package main.java.indi.zyj.coderecord;

import java.util.ArrayList;

public class FindRedundantDirectedConnection {

    int[] father;
    int[] inDegree;
    public int[] findRedundantDirectedConnection(int[][] edges) {

        father = new int[1001];
        int[] res = new int[2];
        int edgeLen = edges.length;
        init();
        inDegree = new int[1001];

        // 表示节点i的入度为indegree[i]
        inDegree[0] = 0;
        for (int i = 0; i < edgeLen; i++) {
            inDegree[edges[i][1]] += 1;
        }

        // 倒序找入度为2的节点所对应的边
        ArrayList<Integer> twoDegree = new ArrayList<>();
        for(int i = edgeLen - 1; i >= 0; i--)
        {
            if(inDegree[edges[i][1]] == 2) {
                twoDegree.add(i);
            }
        }

        if(!twoDegree.isEmpty())
        {
            if(isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {
                return edges[ twoDegree.get(0)];
            }
            return edges[ twoDegree.get(1)];
        }


        for (int i = 0; i < edgeLen; i++) {
            if (!isSame(edges[i][0], edges[i][1])){
                join(edges[i][0], edges[i][1]);
            } else {
                res = edges[i];
            }

        }

        // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
        return getRemoveEdge(edges);

    }


    /**
     * 在有向图里找到删除的那条边，使其变成树
     * @param edges
     * @return 要删除的边
     */
    private int[] getRemoveEdge(int[][] edges) {
        init();
        for(int i = 0; i < edges.length; i++) {
            if(isSame(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
                return edges[i];
            }
            join(edges[i][0], edges[i][1]);
        }
        return null;
    }


    /**
     * 删一条边之后判断是不是树
     * @param edges
     * @param deleteEdge 要删除的边
     * @return  true: 是树， false： 不是树
     */
    private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge)
    {
        init();
        for(int i = 0; i < edges.length; i++)
        {
            if(i == deleteEdge) continue;
            if(isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
                return false;
            }
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }

    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }

    public int find(int u) {
        if (father[u] == u) {
            return u;
        } else {
            father[u] = find(father[u]);
        }
        return father[u];
    }

    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    public void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return;
        }
        father[v] = u;
    }
}
